package com.cuz.series.binarytree;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/***
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/
 */
public class 二叉树1二叉树的中序遍历 {

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2= new TreeNode(2);
        TreeNode treeNode3= new TreeNode(3);
        treeNode1.right=treeNode2;
        treeNode2.left=treeNode3;
        morris(treeNode1);
    }

    public static List<Integer> inorderTraversal1(TreeNode root) {
        if (root == null) {
            return Collections.emptyList();
        }
        List<Integer> list = new LinkedList<>();
        Stack<TreeNode> stackMemory = new Stack<>();
        do {
            while (root != null) {
                stackMemory.push(root);
                root = root.left;
            }
            if (!stackMemory.isEmpty()) {
                root = stackMemory.pop();
                list.add(root.val);
                root = root.right;
            }
        } while (!stackMemory.isEmpty() || root != null);
        return list;
    }


    private static List<Integer> morris(TreeNode node) {
        List<Integer> list = new LinkedList<>();
        TreeNode cur = node;
        while (cur != null) {
            if (cur.left == null) {
                list.add(cur.val);
                cur = cur.right;
            } else {
                TreeNode mostRight = mostRightNodeOf(cur);
                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                } else {
                    mostRight.right = null;
                    list.add(cur.val);
                    cur = cur.right;
                }
            }
        }
        return list;
    }


    private static TreeNode mostRightNodeOf(TreeNode node) {
        TreeNode temp=node;
        node=node.left;

        while (node.right != null&&node.right!=temp) {
            node = node.right;
        }
        return node;
    }
    public static void morrisMidPrint(TreeNode node) {
        TreeNode currentNode = node;
        TreeNode mostRightNodeOfCur = null;
        while (currentNode != null) {
            //一开始初始化为左节点
            mostRightNodeOfCur = currentNode.left;
            if (mostRightNodeOfCur != null) {
                //如果存在右节点，右节点 指向的不是自己（指第一次来到此节点）
                //一直向右
                while (mostRightNodeOfCur.right != null && mostRightNodeOfCur.right != currentNode) {
                    mostRightNodeOfCur = mostRightNodeOfCur.right;
                }
                //此时mostRightNodeOfCur 是左子树的最右节点
                //如果最右节点的右为null 说明是第一次来到此节点
                if (mostRightNodeOfCur.right == null) {
                    //让最右的右节点指向上一层
                    mostRightNodeOfCur.right = currentNode;
                    //自己向左
                    currentNode = currentNode.left;
                    continue;
                } else {
                    //这个节点有左树 说明可以到达两次，这是第二次到达 so 打印
                    System.out.print(currentNode.val+"\t");
                    //第二次来到 让最右指向空
                    mostRightNodeOfCur.right = null;
                }
            } else {
                //当前节点没有左树 ，说明只能到达一次 直接打印
                System.out.print(currentNode.val+"\t");
            }
            currentNode = currentNode.right;
        }
    }
}
